#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        if (l1 == NULL || l2 == NULL)
        {
            if (l1 == NULL && l2 == NULL)
                return NULL;
            if (l1 == NULL)
                return l2;
            else
                return l1;
        }
        ListNode *l = NULL, *tmp = NULL, *ptr = NULL;
        while (l1 != NULL && l2 != NULL)
        {
            if (l1->val < l2->val)
            {
                tmp = l1;
                l1 = l1->next;
            }
            else
            {
                tmp = l2;
                l2 = l2->next;
            }
            if (ptr == NULL)
            {
                l = new ListNode(tmp->val);
                ptr = l;
            }
            else
            {
                l->next = new ListNode(tmp->val);
                l = l->next;
            }
        }
        if (l1 != NULL)
            l->next = l1;
        else
            l->next = l2;
        return ptr;
    }
};